# -*- coding=utf-8-*-
"""
@File:memory_selection
@Author:Created by Han X.Y
@Date:on 2021/8/6 16:12 
"""
class TreeNode:
    def __init__(self,val,left=None,right=None):
        self.val=val
        self.left=left
        self.right=right


"""
先序遍历：
    常规解法：先序遍历利用栈的辅助，在访问完该节点后将子树入栈即可。
"""
class Solution:
    def preorderTraversal(self,root):
        if not root:
            return []
        #利用栈进行临时存储
        res,stack=[],[root]
        while stack:
            #取出一个节点，表示开始访问该节点为根的子树
            node=stack.pop()
            #首先访问该子树(先序)，之后顺序入栈右子树，左子树
            res.append(node.val)
            if node.right:
                stack.append(node.right)
            if node.left:
                stack.append(node.left)
        return  res


"""
中序遍历的思想：
    若节点还有左子树，就把左子树访问完；
    没有左子树可以访问，访问该节点，并尝试访问右子树
"""

class Solution2:
    def inorderTraversal(self,root):
        if not root:
            return []
        #利用栈进行临时存储
        res,stack=[],[]
        #当root为null时，说明已经遍历结束
        while root:
            #存在左子树，入栈并深入左子树
            if root.left:
                stack.append(root)
                root=root.left
            else:
                #否则就可以寻找深入右子树结点
                #对于不能深入右子树的结点，直接访问，此时子树访问结束
                while stack and not root.right:
                    res.append(root.val)
                    root=stack.pop()
                res.append(root.val)#如果可以深入右子树，访问该节点后，深入右子树
                root=root.right
        return res

"""
后序遍历
主要思想：
1.尝试按顺序访问该节点的左右子树
2.当左右子树都访问完毕，才可以访问该节点
因此可以考虑栈的方式，依次将根节点、右孩子、左孩子入栈，以
保证访问次序。由于后续遍历的回溯过程只可能上升一层，因此可以添加临时变量prev
记录刚刚访问的结点。如果当前结点时上次访问结点的父节点，
则说明子树访问完成，可以访问当前结点了。


"""
class Solution3:
    def postorderTraversal(self,root):
        if not root:
            return []
        res,stack=[],[root]
        prev=root#为了判断父子结点关系
        while stack:
            root=stack.pop()
            #如果该节点为叶子节点或者已经访问该结点的子结点
            if (not root.left and not root.right)



